package someTestExcemple.huaweiOd.sort;
//华为OD机试 - 寻找最优的路测线路 - Dijkstra算法（Java 2024 E卷 200分）
//https://blog.csdn.net/guorui_java/article/details/141500591
import java.util.*;
//Dijkstra-like算法通过贪心的思想，每一步选择当前最优的路径
//逐步逼近全局最优解。这种算法在路径搜索问题中非常有效，
//尤其是当路径上的某个值（如信号质量）需要最大化或最小化时。
//Dijkstra算法通常用于求解加权图中的最短路径问题。它通过使用优先队列，每次扩展最短路径节点，逐步找到从起点到终点的最短路径。
//本题使用类似于Dijkstra的思路：从起点开始，每次优先选择当前路径中最小信号值最大的路径进行扩展，
// 直到到达终点。
// 这保证了我们找到的路径是最优的，即路径中的信号最差值尽可能大。
public class SearchTheBestRoute {
    //方向
    private static int[][] direction ={{-1,0},{0,1},{1,0},{0,-1}};
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int R = scanner.nextInt();
        int C = scanner.nextInt();
        int[][] grid = new int[R][C];

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        int result = findBestRouteSignal(grid, R, C);
        System.out.println(result);
    }

    public static int findBestRouteSignal(int[][] grid, int R, int C) {
        // 优先队列，按路径的信号质量从大到小排序
        PriorityQueue<Cell> pq = new PriorityQueue<>((a, b) -> b.minSignal - a.minSignal);
        pq.offer(new Cell(0, 0, grid[0][0]));

        // 标记矩阵，防止重复访问
        boolean[][] visited = new boolean[R][C];
        visited[0][0] = true;
        List<Cell> route  = new ArrayList<>();
        while (!pq.isEmpty()) {
            Cell current = pq.poll();
            route.add(current);
            // 如果到达右下角，返回最优路径的最小信号值
            if (current.x == R - 1 && current.y == C - 1) {
                return current.minSignal;
            }

            // 探索四个方向的相邻栅格
            for (int[] dir : direction) {
                int newX = current.x + dir[0];
                int newY = current.y + dir[1];

                // 检查新坐标是否在边界内且未访问过
                if (newX >= 0 && newX < R && newY >= 0 && newY < C && !visited[newX][newY]) {
                    visited[newX][newY] = true;
                    pq.offer(new Cell(newX, newY, Math.min(current.minSignal, grid[newX][newY])));
                }
            }
        }


        // 如果未能找到路径，返回 -1
        return -1;

    }

    // 定义栅格类，包含其坐标和路径中的最小信号值
    static class Cell {
        int x, y, minSignal;

        public Cell(int x, int y, int minSignal) {
            this.x = x;
            this.y = y;
            this.minSignal = minSignal;
        }

        @Override
        public String toString() {
            return "Cell{" +
                    "x=" + x +
                    ", y=" + y +
                    ", minSignal=" + minSignal +
                    '}';
        }
    }
}
